package practice1_100;

public class Practice121 {
    public int maxProfit(int[] prices) {
        int maxValue=0;
        for( int i=0;i<prices.length;i++){
            for (int j=i+1;j<prices.length;j++){
                maxValue=prices[j]-prices[i]>maxValue?(prices[j]-prices[i]):maxValue;
            }
        }
        return maxValue;
    }

    public static void main(String[] args) {
        Practice121 practice121=new Practice121();
        int a=  practice121.proFit(new int[] {1,5,2,10});
        System.out.println(a);
    }

    public int proFit(int[] prices){
        int n = prices.length;
        // base case: dp[-1][0] = 0, dp[-1][1] = -infinity
        int dp_i_0 = 0, dp_i_1 = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            // dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i])
            dp_i_0 = Math.max(dp_i_0, dp_i_1 + prices[i]);
            // dp[i][1] = max(dp[i-1][1], -prices[i])
            dp_i_1 = Math.max(dp_i_1, -prices[i]);
        }
        return dp_i_0;



    }
}
